C’est l'un des 7 problèmes du millénaire, où la philo vient yinger dans le yang des maths.
P=NP ? C’est une conjecture, un truc qu’on ne sait pas démontrer mais qu’on suppose fortement vrai. Comme le manque de neurones dans le cerveau des anti-IVG, on ne peut pas le démontrer, mais c‘est évident

J’ai abordé le problème sous l’axe philosophico-absurde, n’ayant nullement la prétention de trouver une piste de résolution. Hein y’a 116 mathématiciens qui se viandent depuis des années dessus c’est pas moi avec trois billes et deux cailloux qui vais révolutionner le bouzin. Mais cela m’a emmené beaucoup plus loin que ce que je pensais.

Le problème est formulé par l’Institut Clay, trouvable sur Internet. La question est : Si on considère un problème P, et NP l’opposé du problème. P étant les problèmes dits simples, qu’on peut résoudre dans un temps polynomial (assez court), NP les problèmes plus complexes, et NP Complets les problèmes au moins aussi complexes que tous les NP, que nos machines mettent du temps à résoudre ou ne peuvent résoudre. Existe-t-il des cas où une réponse trouvée « par chance » rapidement peut aboutir aussi prestement avec un algorithme pré-établi  (calculs…). En d’autres termes, les problèmes compliqués sont-ils vraiment différents des problèmes simples ? Y a-t-il un lien entre les cracks boursiers et pourquoi je persiste à utiliser une brosse à dents qui ne ressemble plus à rien ?  Si on transpose à notre vie, pourrait-on mettre au point un algorithme, pour trouver la fin de PI si elle existe ? Pour empêcher l’inflation, le manque de nourriture, détruire les métastases, diriger nos sentiments,  réduire le temps d’attente chez le Service Client Free ? (Vous abusez de ouf les mecs).

On va être amené à étudier la théorie de la complexité, qui pour le coup, porte bien son nom. Problème déjà, c’est quoi la complexité, un truc complexe pour un individu l’est-il forcément pour un autre ?...Beau sujet de discussion. Ca implique de virer l’humain de tout ça, mais c’est défini. La théorie de la complexité vise à étudier en informatique théorique, les ressources nécessaires à un algorithme pour résoudre un problème. Desquelles il a besoin pour trouver la solution.  La principale ressource étant le temps, bien entendu. On a aussi l’espace (en informatique). Il  existe différentes classes de complexité de problèmes, qu’on va transposer à la vie réelle, parce que c’est maxi chiant sinon.  La théorie de la complexité visant principalement à résoudre les problèmes décisionnels (OUI ou NON). Les données des problèmes décisionnels s’appellent les instances. Elles peuvent être positives et permettent de répondre OUI à un problème. Par exemple, étant donné un pays, y a-t-il des chinois dedans ? OUI ou NON. On a la possibilité de chercher toutes les instances positives qui vont permettre de répondre OUI à ce problème. La partie cliché qui nous pousse à répondre OUI car « Boh ils sont partout il doit bien y’en avoir un ou deux ici ». Et il  y a la réponse algorithmique. Imaginons l’algorithme permettant de calculer la population chinoise mondiale et sa répartition, (un genre de recensement niveau légende), on saurait pour chaque pays répondre OUI ou NON.

Et le problème se situe là : Peut-on obtenir la même réponse en un même temps. Et bien Alan Turing, #JeanMichelJaiGagnéLaGuerreAvecEnigma, il a prouvé que non, il existe des questions algorithmiquement indécidables.

Et je me pose cette question : La notion de perfection est présente pour tenter de répondre à ça. Or, on en sait foutrement rien de la perfection. Si la perfection existait, personne ne gagnerait jamais au loto, ou tout le monde gagnerait tout le temps, ce qui est relativement pareil.  Et trouver une démonstration à ce problème permettrait un jour peut être de trouver un algorithme du bonheur, comment atteindre le bonheur.  Oui, mais le bonheur implique sûrement de tolérer des imperfections, ce qui va totalement à l’encontre de la perfection recherchée ici.   Si tant est qu’on arrive à résoudre ce problème, à prouver que P=NP.

Cela engendrerait certainement beaucoup de problèmes, philosophiques déjà, de prouver P=NP. Cela impliquerait qu’en réussissant une parfaite tarte aux fraises, on pourrait éradiquer le SIDA, en suivant l’algorithme de la réussite parfaite. D’un point de vue sécuritaire, problèmes aussi. Par exemple, pour le cryptage des données personnelles et bancaires, le principe de sécurité admis est qu’aucun ordinateur au monde ne pourrait retrouver nos données, mots de passes, numéros... S’il est prouvé un jour que P = NP, il deviendrait concevable que ces données puissent être trouvées et piratées, ce qui nécessiterait de repenser la sécurité confidentielle et bancaire dans son ensemble. Les cartes, les comptes et les ordinateurs risqueraient d'être obsolètes. De manière logique, les sites de transactions flagés « https » et tous les protocoles deviendraient caduques eux aussi. Cela pourrait enclencher de graves crises économiques. En seraient impactés également tous types de flux (informations, marchandises…). On pourrait envisager qu'en suivant un algorithme parfait, on puisse contrer la rotation de la Terre, remonter le temps... Tout  ça parce que P = NP, IMAGINE LE BORDEL MON GARS. A moins que l'on considère que si on parvient à  prouver que P différent de NP est un problème complexe. Si on prouve un jour que P=NP, on serait potentiellement en mesure de résoudre, ce problème complexe, (P différent de NP). Un algorithme parfait pourrait-il lui-même se détruire ? 

Dans tous les cas, on est un serpent obligés de refuser de se mordre la queue mais condamnés à se sentir de plus en plus à l’étroit. Ou alors, on souhaite forcément trouver. La véritable question est : Faut-il accepter d'être le serpent qui se mord la queue, devenant Ouroboros et chercher une solution à l’irrésolvable ? OUI ou NON ?

Clément Bonpoil

Sources :

Travaux du mathématicien allemand Norbert Blum
Encyclopaedia Universalis